{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Distinct Echo Substrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #trie #string #hash-function #rolling-hash"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字典树 #字符串 #哈希函数 #滚动哈希"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: distinctEchoSubstrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #不同的循环子字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串&nbsp;<code>text</code> ，请你返回满足下述条件的&nbsp;<strong>不同</strong> 非空子字符串的数目：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>可以写成某个字符串与其自身相连接的形式（即，可以写为 <code>a&nbsp;+ a</code>，其中 <code>a</code> 是某个字符串）。</li>\n",
    "</ul>\n",
    "\n",
    "<p>例如，<code>abcabc</code>&nbsp;就是&nbsp;<code>abc</code>&nbsp;和它自身连接形成的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>text = &quot;abcabcabc&quot;\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>3 个子字符串分别为 &quot;abcabc&quot;，&quot;bcabca&quot; 和 &quot;cabcab&quot; 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>text = &quot;leetcodeleetcode&quot;\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>2 个子字符串为 &quot;ee&quot; 和 &quot;leetcodeleetcode&quot; 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= text.length &lt;= 2000</code></li>\n",
    "\t<li><code>text</code>&nbsp;只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [distinct-echo-substrings](https://leetcode.cn/problems/distinct-echo-substrings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [distinct-echo-substrings](https://leetcode.cn/problems/distinct-echo-substrings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abcabcabc\"', '\"leetcodeleetcode\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "\n",
    "        mod, base = 10**9 + 7, 31\n",
    "        pre, mul = [0] * (n + 1), [1] + [0] * n\n",
    "        for i in range(1, n + 1):\n",
    "            pre[i] = (pre[i - 1] * base + ord(text[i - 1])-ord('a')+1) % mod\n",
    "            mul[i] = mul[i - 1] * base % mod\n",
    "        \n",
    "        def get_hash(l, r):\n",
    "            return (pre[r + 1] - pre[l] * mul[r - l + 1] % mod + mod) % mod\n",
    "\n",
    "        seen =set()\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                l = j - i\n",
    "                if j + l <= n:\n",
    "                    hash_left = get_hash(i, j - 1)\n",
    "                    if hash_left not in seen and hash_left == get_hash(j, j + l - 1):\n",
    "                        ans += 1\n",
    "                        seen.add(hash_left)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        #满足条件的子串必是偶数长度\n",
    "        res = set()\n",
    "        #for i in range(len(text)):\n",
    "            #for j in range(1, (len(text) - i)//2 + 1, 2):\n",
    "                #i:i+j//2 i+j//2+1:i+j\n",
    "        text = [ord(x) - ord('a') + 1 for x in text]\n",
    "        mod1 = 10 ** 9 + 7\n",
    "        mod2 = 10 ** 9 + 8\n",
    "        b1, b2 = 1, 1\n",
    "        a1, a2 = 27, 28\n",
    "        for j in range(1, (len(text) // 2) + 1):\n",
    "            code11, code12, code21, code22 = 0, 0, 0, 0\n",
    "            for i in range(j):\n",
    "                code11 = (code11 * a1 + text[i]) % mod1\n",
    "                #code12 = (code12 * a2 + text[i]) % mod2\n",
    "                code21 = (code21 * a1 + text[i + j]) % mod1\n",
    "                #code22 = (code22 * a2 + text[i + j]) % mod2\n",
    "            #print(j, code11, code12, code21, code22)\n",
    "            if code11 == code21 and code12 == code22:\n",
    "                res.add((code11, code22)) \n",
    "            for i in range(1, len(text) + 1 - 2 * j):\n",
    "                #i:i+j i+j:i+j*2 n-3:n-2 n-2:n-1 n-5:n-3 n-3:n-1\n",
    "                code11 = ((code11 - b1 * text[i-1]) * a1 + text[i+j-1]) % mod1\n",
    "                #code12 = ((code12 - b2 * text[i-1]) * a2 + text[i+j-1]) % mod2\n",
    "                code21 = ((code21 - b1 * text[i-1+j]) * a1 + text[i+2*j-1]) % mod1\n",
    "                #code22 = ((code22 - b2 * text[i-1+j]) * a2 + text[i+2*j-1]) % mod2\n",
    "                if code11 == code21 and code12 == code22:\n",
    "                    res.add((code11, code22)) \n",
    "            b1 = (b1 * a1) % mod1\n",
    "            #b2 = (b2 * a2) % mod2\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, s: str) -> int:\n",
    "\n",
    "        MOD = 10**9+7\n",
    "        base = 31       # s仅包含小写字母，base可取31\n",
    "        \n",
    "        '''字符编码函数'''\n",
    "        def encode(ch):\n",
    "            return ord(ch) - ord('a') + 1\n",
    "\n",
    "        n = len(s)\n",
    "        '''预处理出前缀字符串的哈希值 和 base进制的幂'''\n",
    "        prefix = [0] * (n+1)    # prefix[i]: 字符串s[0:i]的哈希值\n",
    "        mul = [1] * (n+1)       # mul[i]: base ** i\n",
    "        for i in range(1, n+1):\n",
    "            prefix[i] = ( prefix[i-1] * base + encode(s[i-1]) ) % MOD\n",
    "            mul[i] = mul[i-1] * base % MOD\n",
    "        \n",
    "        ans = 0\n",
    "        visited = set()\n",
    "        for i in range(n-1):\n",
    "            for m in range(1, (n-i)//2+1):      # 目标子串的长度m：[1, (n-i)//2]\n",
    "                '''左侧字符串: s[i, i+m-1], 右侧字符串: s[i+m, i+2m-1]'''\n",
    "                left = ( prefix[i+m] - prefix[i] * mul[m] % MOD + MOD ) % MOD\n",
    "                if left in visited:             # 当前字符已被记录\n",
    "                    continue\n",
    "                right = ( prefix[i+2*m] - prefix[i+m] * mul[m] % MOD + MOD ) % MOD\n",
    "                if left == right:       # 左侧字符串 与 右侧字符串 相同\n",
    "                    visited.add(left)\n",
    "                    ans += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        #满足条件的子串必是偶数长度\n",
    "        res = set()\n",
    "        #for i in range(len(text)):\n",
    "            #for j in range(1, (len(text) - i)//2 + 1, 2):\n",
    "                #i:i+j//2 i+j//2+1:i+j\n",
    "        text = [ord(x) - ord('a') + 1 for x in text]\n",
    "        mod1 = 10 ** 9 + 7\n",
    "        mod2 = 10 ** 9 + 8\n",
    "        b1, b2 = 1, 1\n",
    "        a1, a2 = 27, 28\n",
    "        for j in range(1, (len(text) // 2) + 1):\n",
    "            code11, code12, code21, code22 = 0, 0, 0, 0\n",
    "            for i in range(j):\n",
    "                code11 = (code11 * a1 + text[i]) % mod1\n",
    "                code12 = (code12 * a2 + text[i]) % mod2\n",
    "                code21 = (code21 * a1 + text[i + j]) % mod1\n",
    "                code22 = (code22 * a2 + text[i + j]) % mod2\n",
    "            #print(j, code11, code12, code21, code22)\n",
    "            if code11 == code21 and code12 == code22:\n",
    "                res.add((code11, code22)) \n",
    "            for i in range(1, len(text) + 1 - 2 * j):\n",
    "                #i:i+j i+j:i+j*2 n-3:n-2 n-2:n-1 n-5:n-3 n-3:n-1\n",
    "                code11 = ((code11 - b1 * text[i-1]) * a1 + text[i+j-1]) % mod1\n",
    "                code12 = ((code12 - b2 * text[i-1]) * a2 + text[i+j-1]) % mod2\n",
    "                code21 = ((code21 - b1 * text[i-1+j]) * a1 + text[i+2*j-1]) % mod1\n",
    "                code22 = ((code22 - b2 * text[i-1+j]) * a2 + text[i+2*j-1]) % mod2\n",
    "                if code11 == code21 and code12 == code22:\n",
    "                    res.add((code11, code22)) \n",
    "            b1 = (b1 * a1) % mod1\n",
    "            b2 = (b2 * a2) % mod2\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "        presum = [0]\n",
    "        mul = [1]\n",
    "        base = 131\n",
    "        mod = 2 ** 63 - 1 \n",
    "        for c in text:\n",
    "            presum.append((presum[-1] * base + ord(c) - ord('a')) % mod)\n",
    "            mul.append(mul[-1] * base % mod)  \n",
    "        def get_hash(i, j):\n",
    "            return (presum[j + 1] - presum[i] * mul[j + 1 - i] % mod + mod) % mod\n",
    "        res = 0\n",
    "        for l in range(1, n // 2 + 1):\n",
    "            visit = set()\n",
    "            for i in range(n - 2 * l + 1):\n",
    "                j = i + l \n",
    "                if get_hash(i, j - 1) == get_hash(j, j + l - 1) and get_hash(i, j - 1) not in visit:\n",
    "                    visit.add(get_hash(i, j - 1))\n",
    "                    res += 1 \n",
    "        return res \n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "        base = 31\n",
    "        mod = 10**9+7\n",
    "        # 2.预处理\n",
    "        # pre[i]表示字符串text[0:i]的哈希值\n",
    "        pre = [0]*(n+1)\n",
    "        # mul[i]表示base的i次方\n",
    "        mul = [1] + [0]*(n)\n",
    "        for i in range(1,n+1):\n",
    "            pre[i] = (pre[i-1] * 31 + ord(text[i-1]))%mod\n",
    "            mul[i] = mul[i-1] * base % mod\n",
    "        def get_hash(l,r):\n",
    "            return (pre[r+1] - pre[l]*mul[r-l+1])%mod\n",
    "        \n",
    "        seen = set()\n",
    "        ans = 0\n",
    "        # 1.枚举子字符串的i,j\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n+1):\n",
    "                l = j - i\n",
    "                if j + l <= n:\n",
    "                    hash_left = get_hash(i,j-1)\n",
    "                    if hash_left not in seen and hash_left == get_hash(j,j+l-1):\n",
    "                        ans += 1\n",
    "                        seen.add(hash_left)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Rabin-Karp 算法\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "        base = 31\n",
    "        mod = 10**9+7\n",
    "        # 2.预处理\n",
    "        # pre[i]表示字符串text[0:i]的哈希值\n",
    "        pre = [0]*(n+1)\n",
    "        # mul[i]表示base的i次方\n",
    "        mul = [1] + [0]*(n)\n",
    "        for i in range(1,n+1):\n",
    "            pre[i] = (pre[i-1] * 31 + ord(text[i-1]))%mod\n",
    "            mul[i] = mul[i-1] * base % mod\n",
    "        def get_hash(l,r):\n",
    "            return (pre[r+1] - pre[l]*mul[r-l+1])%mod\n",
    "        \n",
    "        seen = set()\n",
    "        ans = 0\n",
    "        # 1.枚举子字符串的i,j\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n+1):\n",
    "                l = j - i\n",
    "                if j + l <= n:\n",
    "                    hash_left = get_hash(i,j-1)\n",
    "                    if hash_left not in seen and hash_left == get_hash(j,j+l-1):\n",
    "                        ans += 1\n",
    "                        seen.add(hash_left)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, s: str) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        base=31\n",
    "        encode={}\n",
    "        for i in range(26):\n",
    "            ch = chr(ord('a') + i)\n",
    "            encode[ch] = i + 1\n",
    "        n=len(s)\n",
    "        prefix=[0]*(n+1)\n",
    "        mul=[1]*(n+1)\n",
    "\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            prefix[i]=(prefix[i-1]*base+encode[s[i-1]])%MOD\n",
    "            mul[i]= mul[i-1]*base%MOD\n",
    "\n",
    "        res=0\n",
    "        vis=set()\n",
    "        for i in range(n-1):\n",
    "            for m in range(1,(n-i)//2+1):\n",
    "                left = (prefix[i+m]-prefix[i]*mul[m])%MOD\n",
    "                if left in vis:\n",
    "                    continue\n",
    "                right= (prefix[i+2*m]-prefix[i+m]*mul[m])%MOD\n",
    "                if left==right:\n",
    "                    vis.add(left)\n",
    "                    res+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Rabin-Karp 算法\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "        # 核心思想:用一个哈希数表示一个字符串\n",
    "        base = 31\n",
    "        mod = 10**9+7\n",
    "        n = len(text)\n",
    "        # pre[i]表示text[0:i]的哈希值\n",
    "        pre = [0]*(n+1)\n",
    "        mul = [1]+[0]*n\n",
    "        for i in range(n):\n",
    "            pre[i+1] = (pre[i]*base + ord(text[i]))%mod\n",
    "            mul[i+1] = mul[i]*base%mod\n",
    "        # 获得text[l,r]的哈希值这里取到r\n",
    "        def get_hash(l,r):\n",
    "            return (pre[r+1]-pre[l]*mul[r-l+1])%mod\n",
    "        # 枚举a + a字符串的一半,i:j,另一半为j+1:2j-i+1\n",
    "        ans = 0\n",
    "        seen = set()\n",
    "        for i in range(n):\n",
    "            for j in range(i,n):\n",
    "                if 2*j-i+1 < n:\n",
    "                    hash_left = get_hash(i,j)\n",
    "                    if hash_left not in seen and hash_left == get_hash(j+1,2*j-i+1):\n",
    "                        ans += 1\n",
    "                        seen.add(hash_left)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "#         pre = [0]*(n+1)\n",
    "#         # mul[i]表示base的i次方\n",
    "#         mul = [1] + [0]*(n)\n",
    "#         for i in range(1,n+1):\n",
    "#             pre[i] = (pre[i-1] * 31 + ord(text[i-1]))%mod\n",
    "#             mul[i] = mul[i-1] * base % mod\n",
    "#         def get_hash(l,r):\n",
    "#             return (pre[r+1] - pre[l]*mul[r-l+1])%mod\n",
    "        \n",
    "#         seen = set()\n",
    "#         ans = 0\n",
    "#         # 1.枚举子字符串的i,j\n",
    "#         for i in range(n):\n",
    "#             for j in range(i+1,n+1):\n",
    "#                 l = j - i\n",
    "#                 if j + l <= n:\n",
    "#                     hash_left = get_hash(i,j-1)\n",
    "#                     if hash_left not in seen and hash_left == get_hash(j,j+l-1):\n",
    "#                         ans += 1\n",
    "#                         seen.add(hash_left)\n",
    "#         return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Rabin-Karp 算法\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "        # 核心思想:用一个哈希数表示一个字符串\n",
    "        base = 31\n",
    "        mod = 10**9+7\n",
    "        n = len(text)\n",
    "        # pre[i]表示text[0:i]的哈希值\n",
    "        pre = [0]*(n+1)\n",
    "        mul = [1]+[0]*n\n",
    "        for i in range(n):\n",
    "            pre[i+1] = (pre[i]*base + ord(text[i]))%mod\n",
    "            mul[i+1] = mul[i]*base%mod\n",
    "        # 获得text[l,r]的哈希值这里取到r\n",
    "        def get_hash(l,r):\n",
    "            return (pre[r+1]-pre[l]*mul[r-l+1])%mod\n",
    "        # 枚举a + a字符串的一半,i:j,另一半为j+1:2j-i+1\n",
    "        ans = 0\n",
    "        seen = set()\n",
    "        for i in range(n):\n",
    "            for j in range(i,n):\n",
    "                if 2*j-i+1 < n:\n",
    "                    hash_left = get_hash(i,j)\n",
    "                    if hash_left not in seen and hash_left == get_hash(j+1,2*j-i+1):\n",
    "                        ans += 1\n",
    "                        seen.add(hash_left)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "        seen = set()\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if j * 2 - i <= n and text[i:j] == text[j:j*2-i] and text[i:j] not in seen:\n",
    "                    ans += 1\n",
    "                    seen.add(text[i:j])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "        presum = [0]\n",
    "        mul = [1]\n",
    "        base = 131\n",
    "        mod = 2 ** 63 - 1 \n",
    "        for c in text:\n",
    "            presum.append((presum[-1] * base + ord(c) - ord('a')) % mod)\n",
    "            mul.append(mul[-1] * base % mod)  \n",
    "        def get_hash(i, j):\n",
    "            return (presum[j + 1] - presum[i] * mul[j + 1 - i] % mod + mod) % mod\n",
    "        res = 0\n",
    "        for l in range(1, n // 2 + 1):\n",
    "            visit = set()\n",
    "            for i in range(n - 2 * l + 1):\n",
    "                j = i + l \n",
    "                if get_hash(i, j - 1) == get_hash(j, j + l - 1) and get_hash(i, j - 1) not in visit:\n",
    "                    visit.add(get_hash(i, j - 1))\n",
    "                    res += 1 \n",
    "        return res \n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "        seen = set()\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if j * 2 - i <= n and text[i:j] == text[j:j*2-i] and text[i:j] not in seen:\n",
    "                    ans += 1\n",
    "                    seen.add(text[i:j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "        seen = set()\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if j * 2 - i <= n and text[i:j] == text[j:j*2-i] and text[i:j] not in seen:\n",
    "                    ans += 1\n",
    "                    seen.add(text[i:j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        ans = 0\n",
    "        visit = set()\n",
    "        for i in range(len(text)) :\n",
    "            for j in range(i+1, len(text)) :\n",
    "                if text[i:j] == text[j:j+(j-i)] and  text[i:j] not in visit:\n",
    "                    visit.add(text[i:j])\n",
    "                    ans += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "        seen = set()\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n+1):\n",
    "                if j*2-i <= n and text[i:j] == text[j:j*2-i] and text[i:j] not in seen:\n",
    "                    ans += 1\n",
    "                    seen.add(text[i:j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        n, visited, res = len(text), set(), 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if j * 2 - i <= n and text[i:j] == text[j:j*2-i] and text[i:j] not in visited:\n",
    "                    res += 1\n",
    "                    visited.add(text[i:j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        def prefun(s):\n",
    "            ans=0\n",
    "            n=len(s)\n",
    "            pi=[0]*n\n",
    "            j=0\n",
    "            for i in range(1,n):\n",
    "                while j>0 and s[i]!=s[j]:\n",
    "                    j=pi[j-1]\n",
    "                if s[i]==s[j]:\n",
    "                    j+=1\n",
    "                pi[i]=j\n",
    "                m=i+1\n",
    "                if j!=0 and m%(m-j)==0 and m//(m-j)%2==0:\n",
    "                    if s[:m//2] not in visited:\n",
    "                        visited.add(s[:m//2])\n",
    "                        ans+=1\n",
    "            return ans\n",
    "\n",
    "        n=len(text)\n",
    "        visited=set()\n",
    "        ans=0\n",
    "        for i in range(n-1):\n",
    "            ans+=prefun(text[i:])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        '''\n",
    "        res = set()\n",
    "        #for i in range(len(text)):\n",
    "            #for j in range(1, (len(text) - i)//2 + 1, 2):\n",
    "                #i:i+j//2 i+j//2+1:i+j\n",
    "        text = [ord(x) - ord('a') + 1 for x in text]\n",
    "        mod1 = 10 ** 9 + 7\n",
    "        mod2 = 10 ** 9 + 8\n",
    "        b1, b2 = 1, 1\n",
    "        a1, a2 = 27, 28\n",
    "        for j in range(1, (len(text) // 2) + 1):\n",
    "            code11, code12, code21, code22 = 0, 0, 0, 0\n",
    "            for i in range(j):\n",
    "                code11 = (code11 * a1 + text[i]) % mod1\n",
    "                #code12 = (code12 * a2 + text[i]) % mod2\n",
    "                code21 = (code21 * a1 + text[i + j]) % mod1\n",
    "                #code22 = (code22 * a2 + text[i + j]) % mod2\n",
    "            #print(j, code11, code12, code21, code22)\n",
    "            if code11 == code21 and code12 == code22:\n",
    "                res.add((code11, code22)) \n",
    "            for i in range(1, len(text) + 1 - 2 * j):\n",
    "                #i:i+j i+j:i+j*2 n-3:n-2 n-2:n-1 n-5:n-3 n-3:n-1\n",
    "                code11 = ((code11 - b1 * text[i-1]) * a1 + text[i+j-1]) % mod1\n",
    "                #code12 = ((code12 - b2 * text[i-1]) * a2 + text[i+j-1]) % mod2\n",
    "                code21 = ((code21 - b1 * text[i-1+j]) * a1 + text[i+2*j-1]) % mod1\n",
    "                #code22 = ((code22 - b2 * text[i-1+j]) * a2 + text[i+2*j-1]) % mod2\n",
    "                if code11 == code21 and code12 == code22:\n",
    "                    res.add((code11, code22)) \n",
    "            b1 = (b1 * a1) % mod1\n",
    "            #b2 = (b2 * a2) % mod2\n",
    "        return len(res)\n",
    "        '''\n",
    "        res = set()\n",
    "        n = len(text)\n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                if i + 2 * j > n:\n",
    "                    break\n",
    "                if text[i:i + j] == text[i + j:i + 2 * j]:\n",
    "                    res.add(text[i:i+j])\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "        base = 31\n",
    "        mod = 10**9+7\n",
    "        # 2.预处理\n",
    "        # pre[i]表示字符串text[0:i]的哈希值\n",
    "        pre = [0]*(n+1)\n",
    "        # mul[i]表示base的i次方\n",
    "        mul = [1] + [0]*(n)\n",
    "        for i in range(1,n+1):\n",
    "            pre[i] = (pre[i-1] * 31 + ord(text[i-1]))%mod\n",
    "            mul[i] = mul[i-1] * base % mod\n",
    "        def get_hash(l,r):\n",
    "            return (pre[r+1] - pre[l]*mul[r-l+1])%mod\n",
    "        \n",
    "        seen = {x:set() for x in range(n)}\n",
    "        ans = 0\n",
    "        # 1.枚举子字符串的i,j\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n+1):\n",
    "                l = j - i\n",
    "                if j + l <= n:\n",
    "                    hash_left = get_hash(i,j-1)\n",
    "                    if hash_left not in seen[l-1] and hash_left == get_hash(j,j+l-1):\n",
    "                        ans += 1\n",
    "                        seen[l-1].add(hash_left)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        ans = set()\n",
    "        for i in range(1, len(text) // 2 + 1):\n",
    "            k = 0\n",
    "            for j in range(len(text) - i):\n",
    "                if text[j] == text[j + i]:\n",
    "                    k += 1\n",
    "                else:\n",
    "                    k = 0\n",
    "                if k >= i:\n",
    "                    ans.add(text[j - i + 1:j + 1])\n",
    "        return len(ans)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        pool = set()\n",
    "        cnt=0\n",
    "        for i in range(len(text)):\n",
    "            for j in range(i+1,len(text)):\n",
    "                if 2*j-i<=len(text):\n",
    "                    if text[i:j]==text[j:2*j-i] and text[i:j] not in pool:\n",
    "                        pool.add(text[i:j])\n",
    "                        cnt+=1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    # class node():\n",
    "    #     def __init__(self, val, next=None):\n",
    "    #         self.val = val\n",
    "    #         self.next = next\n",
    "\n",
    "    def distinctEchoSubstrings(self, text):\n",
    "        \"\"\"\n",
    "        :type text: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        num = 0\n",
    "        mp = {}\n",
    "        seen = set()\n",
    "        for i in range(len(text)):\n",
    "            c = text[i]\n",
    "            # If not seen: move on\n",
    "            if c not in mp:\n",
    "                mp[c] = [i]\n",
    "            # Otherwise check for echo substrings\n",
    "            else:\n",
    "                for prev_i in mp[c]:\n",
    "                    if text[prev_i: i] == text[i: i + i - prev_i] and text[prev_i: i] not in seen:\n",
    "                        num += 1\n",
    "                        seen.add(text[prev_i: i])\n",
    "                mp[c].append(i)\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        # 在给定字符 s 中找到两个连续且相等的字符片段\n",
    "        def kmp(s):\n",
    "            ans = 0\n",
    "            n = len(s)\n",
    "            nxt = [0] * n \n",
    "            j = 0\n",
    "            for i in range(1, n):\n",
    "                while j > 0 and s[i] != s[j]:\n",
    "                    j = nxt[j-1]\n",
    "                if s[i] == s[j]:\n",
    "                    j += 1\n",
    "                nxt[i] = j\n",
    "\n",
    "                m = i + 1\n",
    "                if j != 0 and m % (m - j) == 0 and m // (m-j) % 2 == 0:\n",
    "                    '''【m 需为 m-j 的偶数倍】'''\n",
    "                    if s[:m//2] not in visited:     # 当前前缀字符串的一半满足要求\n",
    "                        visited.add(s[:m//2])       # 若不重复，则可计入\n",
    "                        ans += 1\n",
    "\n",
    "            return ans\n",
    "        \n",
    "        n = len(text)\n",
    "        visited = set()\n",
    "        ans  = 0\n",
    "        for i in range(n-1):\n",
    "            ans += kmp(text[i:])\n",
    "        \n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "        pre = [0] * (n + 1)\n",
    "        mul = [1] + [0] * (n)\n",
    "\n",
    "        base, mod = 31, 10 ** 9 +7\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            pre[i] = (pre[i-1] * base + ord(text[i-1])) % mod\n",
    "            mul[i] = mul[i-1] * base % mod\n",
    "        \n",
    "        def gethase(l, r):\n",
    "            return (pre[r + 1] - pre[l] * mul[r - l + 1] % mod + mod) % mod\n",
    "        \n",
    "        vis = {x : set() for x in range(n)}\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                l = j - 1 - i + 1\n",
    "                if j + l - 1 >= n:\n",
    "                    continue\n",
    "                hash_left = gethase(i, j - 1)\n",
    "                if hash_left not in vis[l - 1] and hash_left == gethase(j, j + l - 1):\n",
    "                    ans += 1\n",
    "                    vis[l-1].add(hash_left)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        def kmp(s):\n",
    "            n = len(s)\n",
    "            nxt = [0] * n\n",
    "            j = 0\n",
    "            for i in range(1, n):\n",
    "                while j > 0 and s[i] != s[j]:\n",
    "                    j = nxt[j-1]\n",
    "                if s[i] == s[j]:\n",
    "                    j += 1\n",
    "                nxt[i] = j\n",
    "                m = i + 1\n",
    "                if j != 0 and m % (m - j) == 0 and m // (m-j) % 2 == 0:\n",
    "                    if s[:(m//2)] not in visited:\n",
    "                        visited.add(s[:(m//2)])\n",
    "            return nxt\n",
    "      \n",
    "        visited = set()\n",
    "        for i in range(len(text)-1):\n",
    "            nxt = kmp(text[i:])\n",
    "        return len(visited)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        def kmp(s):\n",
    "            n = len(s)\n",
    "            pi = [0] * n\n",
    "            ans = j = 0\n",
    "            for i in range(1, n):\n",
    "                while j > 0 and s[i] != s[j]:\n",
    "                    j = pi[j - 1]\n",
    "                if s[i] == s[j]:\n",
    "                    j += 1\n",
    "                pi[i] = j\n",
    "                m = i + 1\n",
    "                \n",
    "                if j != 0 and m % (m - j) == 0 and m // (m - j) % 2 == 0:\n",
    "                    if s[:m//2] not in vis:\n",
    "                        vis.add(s[:m//2])\n",
    "                        ans += 1\n",
    "            return ans\n",
    "        \n",
    "        vis = set()\n",
    "        return sum(kmp(text[i:]) for i in range(len(text)-1))\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        sett=set()\n",
    "        base=31\n",
    "        mod=10**9+7\n",
    "\n",
    "        basepow=[1]\n",
    "        summ=[0]\n",
    "        for i in range(n):\n",
    "            summ.append((summ[-1]*base+ord(s[i]))%mod)\n",
    "            basepow.append((basepow[-1]*base)%mod) \n",
    "\n",
    "        def get(l,r):\n",
    "            return (summ[r+1]-summ[l]*basepow[r-l+1])%mod\n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i,n):\n",
    "                l=j-i+1\n",
    "                if l%2:continue\n",
    "                if get(i,(i+j)//2)==get((i+j)//2+1,j):\n",
    "                    sett.add(s[i:(i+j)//2+1])\n",
    "\n",
    "        return len(sett)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "        pre = [0] * (n + 1)\n",
    "        mul = [1] + [0] * n\n",
    "        base = 31\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            pre[i] = (pre[i-1] * base + ord(text[i-1])) % mod\n",
    "            mul[i] = mul[i-1] * base % mod \n",
    "        \n",
    "        def gethash(l, r):\n",
    "            return (pre[r + 1] - pre[l] * mul[r - l + 1] % mod + mod) % mod\n",
    "        \n",
    "        vis = {x : set() for x in range(n)}\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                l = j - i\n",
    "                if j + l -1 >= n:\n",
    "                    continue\n",
    "                curhash = gethash(i, j-1)\n",
    "                otherhash = gethash(j, j+l-1)\n",
    "                if not curhash in vis[l-1] and curhash == otherhash:\n",
    "                    ans += 1\n",
    "                    vis[l-1].add(curhash)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "        seen = set()\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if j * 2 - i <= n and text[i: j] == text[j: 2 * j - i] and text[i: j] not in seen:\n",
    "                    ans += 1\n",
    "                    seen.add(text[i: j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        def kmp(s):\n",
    "            n, ans = len(s), 0\n",
    "            nxt = [0] * n\n",
    "            j = 0\n",
    "            for i in range(1, n):\n",
    "                while j > 0 and s[i] != s[j]:\n",
    "                    j = nxt[j-1]\n",
    "                if s[i] == s[j]:\n",
    "                    j += 1\n",
    "                nxt[i] = j\n",
    "                m = i + 1\n",
    "                if j != 0 and m % (m - j) == 0 and m // (m-j) % 2 == 0:\n",
    "                    if s[:(m//2)] not in visited:\n",
    "                        visited.add(s[:(m//2)])\n",
    "                        ans += 1\n",
    "            return ans\n",
    "      \n",
    "        visited = set()\n",
    "        ans = 0\n",
    "        for i in range(len(text)-1):\n",
    "            ans += kmp(text[i:])\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 枚举\n",
    "    def distinctEchoSubstrings2(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "        seen = set()\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if j * 2 - i <= n and text[i:j] == text[j:j*2-i] and text[i:j] not in seen:\n",
    "                    ans += 1\n",
    "                    seen.add(text[i:j])\n",
    "        return ans\n",
    "        \n",
    "    # 滚动哈希 + 前缀和\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "\n",
    "        mod, base = 10**9 + 7, 31\n",
    "        pre, mul = [0] * (n + 1), [1] + [0] * n\n",
    "        for i in range(1, n + 1):\n",
    "            pre[i] = (pre[i - 1] * base + ord(text[i - 1])) % mod\n",
    "            mul[i] = mul[i - 1] * base % mod\n",
    "        \n",
    "        def get_hash(l, r):\n",
    "            return (pre[r + 1] - pre[l] * mul[r - l + 1] % mod + mod) % mod\n",
    "\n",
    "        seen = {x: set() for x in range(n)}\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                l = j - i\n",
    "                if j + l <= n:\n",
    "                    hash_left = get_hash(i, j - 1)\n",
    "                    if hash_left not in seen[l - 1] and hash_left == get_hash(j, j + l - 1):\n",
    "                        ans += 1\n",
    "                        seen[l - 1].add(hash_left)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        s = set()\n",
    "        str = text\n",
    "        for i in range(1, len(str) // 2+1):\n",
    "            for j in range(len(str)-2*i+1) :\n",
    "                # print(str[j:j + i],str[j + i:j + i + i])\n",
    "                if (str[j:j + i] == str[j + i:j + i + i]):\n",
    "                    s.add(str[j:j + i])\n",
    "        return len(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "        pre = [0] * (n + 1)\n",
    "        mul = [1] + [0] * (n)\n",
    "\n",
    "        base, mod = 31, 10 ** 9 +7\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            pre[i] = (pre[i-1] * base + ord(text[i-1])) % mod\n",
    "            mul[i] = mul[i-1] * base % mod\n",
    "        \n",
    "        def gethase(l, r):\n",
    "            return (pre[r + 1] - pre[l] * mul[r - l + 1] + mod) % mod\n",
    "        \n",
    "        vis = {x : set() for x in range(n)}\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                l = j - 1 - i + 1\n",
    "                if j + l - 1 >= n:\n",
    "                    continue\n",
    "                hash_left = gethase(i, j - 1)\n",
    "                if hash_left not in vis[l - 1] and hash_left == gethase(j, j + l - 1):\n",
    "                    ans += 1\n",
    "                    vis[l-1].add(hash_left)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    # class node():\n",
    "    #     def __init__(self, val, next=None):\n",
    "    #         self.val = val\n",
    "    #         self.next = next\n",
    "\n",
    "    def distinctEchoSubstrings(self, text):\n",
    "        \"\"\"\n",
    "        :type text: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        num = 0\n",
    "        mp = {}\n",
    "        seen = set()\n",
    "        added = set()\n",
    "        for i in range(len(text)):\n",
    "            c = text[i]\n",
    "            # If not seen: move on\n",
    "            if c not in mp:\n",
    "                mp[c] = [i]\n",
    "            # Otherwise check for echo substrings\n",
    "            else:\n",
    "                for prev_i in mp[c]:\n",
    "                    prev_str = text[prev_i: i]\n",
    "                    curr_str = text[i: 2*i - prev_i]\n",
    "                    if curr_str == prev_str and curr_str not in added:\n",
    "                        added.add(curr_str)\n",
    "                        num += 1\n",
    "                mp[c].append(i)\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "\n",
    "        MOD, BASE = 1000000007, 31\n",
    "        pre, mul = [0 for _ in range(n + 1)], [0 for _ in range(n + 1)]\n",
    "        mul[0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            pre[i] = (pre[i-1] * BASE + ord(text[i-1])) % MOD\n",
    "            mul[i] = mul[i-1] * BASE % MOD\n",
    "\n",
    "        def hash(l, r):\n",
    "            return  (pre[r+1] - pre[l] * mul[r-l+1] % MOD  + MOD) % MOD\n",
    "\n",
    "        d = {i: set() for i in range(n)}\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                l = j - i\n",
    "                if j + l <= n:\n",
    "                    hash_left = hash(i, j - 1)\n",
    "                    if hash_left not in d[l] and hash_left == hash(j, j+l-1):\n",
    "                        ans += 1\n",
    "                        d[l].add(hash_left)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        def getNxt(s):\n",
    "            nxt = [0] * len(s)\n",
    "            i, j = 1, 0\n",
    "            while i < len(s):\n",
    "                if s[i] == s[j]:\n",
    "                    j += 1\n",
    "                    nxt[i] = j\n",
    "                    i += 1\n",
    "                elif j:\n",
    "                    j = nxt[j - 1]\n",
    "                else:\n",
    "                    i += 1\n",
    "            return nxt\n",
    "\n",
    "        ans = set()\n",
    "        for i in range(len(text)):\n",
    "            nxt = getNxt(text[i:])\n",
    "            for j, v in enumerate(nxt):\n",
    "                if not v or (j + 1) % 2:\n",
    "                    continue\n",
    "                s = text[i:i + j + 1]\n",
    "                if j + 1 <= 2 * v and s and s[:len(s) // 2] == s[len(s) // 2:]:\n",
    "                    ans.add(s[:j + 1])\n",
    "        return len(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get_next(self, needle: str):\n",
    "        n = len(needle)\n",
    "        next = [0] * n\n",
    "        cnt = 0\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            k = next[i-1]                       # NOTE 先以第 i-1 个字符的公共前后缀为搜索点\n",
    "            found = True \n",
    "            while needle[i] != needle[k]:\n",
    "                if k == 0:\n",
    "                    found = False\n",
    "                    break                       # NOTE 漏掉死循环\n",
    "                else:\n",
    "                    k = next[k-1]\n",
    "            if found:\n",
    "                next[i] = k+1\n",
    "            \n",
    "            m = i+1  \n",
    "            if next[i] != -1 and m % (m-next[i]) == 0 and m // (m-next[i]) % 2 == 0:            # NOTE 周期的个数是 2 的倍数\n",
    "                if needle[: i+1] not in self.seen:\n",
    "                    self.seen.add(needle[: i+1])\n",
    "                    cnt += 1\n",
    "                                            \n",
    "        return cnt \n",
    "    \n",
    "    def kmp(self, main_str, sub_str):\n",
    "        n, m = len(main_str), len(sub_str)\n",
    "        next = self.get_next(sub_str)\n",
    "\n",
    "        i, j = 0, 0 \n",
    "        while i <= n-1:\n",
    "            if main_str[i] == sub_str[j]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "            elif j == 0:\n",
    "                i += 1\n",
    "            else:\n",
    "                j = next[j-1]\n",
    "            if j == m:\n",
    "                return i - m\n",
    "        \n",
    "        return -1\n",
    "\n",
    "    def distinctEchoSubstrings(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        self.seen = set()\n",
    "        for i in range(len(s)):\n",
    "            ans += self.get_next(s[i:])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        n, visited, res = len(text), set(), 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if j * 2 - i <= n and text[i:j] == text[j:j*2-i] and text[i:j*2-i] not in visited:\n",
    "                    res += 1\n",
    "                    visited.add(text[i:j*2-i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        def getNxt(s):\n",
    "            nxt = [0] * len(s)\n",
    "            i, j = 1, 0\n",
    "            while i < len(s):\n",
    "                if s[i] == s[j]:\n",
    "                    j += 1\n",
    "                    nxt[i] = j\n",
    "                    i += 1\n",
    "                elif j:\n",
    "                    j = nxt[j - 1]\n",
    "                else:\n",
    "                    i += 1\n",
    "            return nxt\n",
    "\n",
    "        ans = set()\n",
    "        for i in range(len(text)):\n",
    "            nxt = getNxt(text[i:])\n",
    "            for j, v in enumerate(nxt):\n",
    "                if not v or (j + 1) % 2:\n",
    "                    continue\n",
    "                if (j + 1) % (j + 1 - v) == 0 and (j + 1) // (j + 1 - v) % 2 == 0:\n",
    "                    ans.add(text[i:i + j + 1])\n",
    "        return len(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "        ans = set()\n",
    "        P, M = 31, 2 ** 64 - 1\n",
    "        h, p = [0] * (n + 1), [1] * (n + 1)\n",
    "        for i in range(n):\n",
    "            h[i + 1] = (h[i] * P + ord(text[i])) % M\n",
    "            p[i + 1] = p[i] * P  % M\n",
    "            \n",
    "        \n",
    "        left, right = 0, n // 2 + 1\n",
    "        for m in range(1, right):\n",
    "            for i in range(n - 2 * m + 1):\n",
    "                h1 = (h[i + m] - h[i] * p[m]) % M\n",
    "                h2 = (h[i + 2 * m] - h[i + m] * p[m]) % M\n",
    "                if h1 == h2:\n",
    "                    ans.add(text[i:i + 2 * m])\n",
    "        \n",
    "\n",
    "        return len(ans)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctEchoSubstrings(self, text: str) -> int:\n",
    "        all_pat = set()\n",
    "        count = 0\n",
    "        i = 0\n",
    "        while i < len(text):\n",
    "            for j in range(i+1,len(text)):\n",
    "                if j * 2 - i <= len(text) and text[i:j] == text[j:j*2-i] and text[i:j] not in all_pat:\n",
    "                    all_pat.add(text[i:j])\n",
    "                    count += 1\n",
    "            i += 1\n",
    "        print(all_pat)\n",
    "        return count\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
